package AVLTree;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: ling
 * Date: 2022-11-22
 * Time: 10:34
 */
public class AVLTree {
    static class TreeNode {
        public int val;//值
        public int bf;//平衡因子(右子树高度-左子树高度）
        public TreeNode left;//左孩子引用
        public TreeNode right;//右孩子引用
        public TreeNode parent;//父亲节点的引用

        public TreeNode(int val) {
            this.val = val;
        }
    }
    public TreeNode root;//根节点

    public boolean insert(int val) {
        TreeNode node = new TreeNode(val);
        if(root == null) {
            root = node;
            return true;
        }
        TreeNode parent = null;
        TreeNode cur = root;
        while(cur!=null) {
            if(cur.val<val) {
                parent = cur;
                cur= cur.right;
            } else if(cur.val==val) {
                return false;
            } else {
                parent = cur;
                cur = cur.left;
            }
        }
        //cur==null
        if(parent.val<val) {
            parent.right = node;
        } else {
            parent.left = node;
        }
        node.parent = parent;
        cur = node;
        //调节平衡因子
        while(parent!=null) {
            if(parent.left==cur) {
                parent.bf--;
            } else {
                parent.bf++;
            }
            if(parent.bf==0) {
                break;
            } else if(parent.bf==1||parent.bf==-1) {
                cur = parent;
                parent = cur.parent;
            } else {
                if(parent.bf==2) {
                    if(cur.bf==1) {
                        rotateLeft(parent);
                    } else {
                        //cur.bf==-1
                        rotateRL(parent);
                    }
                } else {
                    //parent.bf==-2
                    if(cur.bf==1) {
                        rotateLR(parent);
                    } else {
                        //cur.bf==-1
                        rotateRight(parent);
                    }
                }
                //完成一次旋转之后就能够达成平衡，直接break
                break;
            }
        }
        return true;
    }

    /**
     * 右左双旋
     * @param parent
     */
    private void rotateRL(TreeNode parent) {
        TreeNode subR = parent.right;
        TreeNode subRL = subR.left;
        int bf = subRL.bf;
        rotateRight(parent.right);
        rotateLeft(parent);
        if(bf==-1) {
            subR.bf=1;
            subRL.bf=0;
            parent.bf=0;
        } else if(bf==1) {
            subR.bf = 0;
            subRL.bf = 0;
            parent.bf = -1;
        }
        //bf==0不需要处理
    }
    /**
     * 左右双旋
     * @param parent
     */
    private void rotateLR(TreeNode parent) {
        TreeNode subL = parent.left;
        TreeNode subLR = subL.right;
        int bf = subLR.bf;
        rotateLeft(parent.left);
        rotateRight(parent);
        //分情况调整，平衡因子
        if(bf==-1) {
            subL.bf=0;
            subLR.bf=0;
            parent.bf=1;
        } else if(bf==1) {
            subL.bf=-1;
            subLR.bf=0;
            parent.bf=0;

        }
        //当bf==0不需要做任何处理
    }

    /**
     * 左单旋
     * @param parent
     */
    private void rotateLeft(TreeNode parent) {
        TreeNode subR = parent.right;
        TreeNode subRL = subR.left;
        //记录一下parent的父亲节点
        TreeNode pParent = parent.parent;
        parent.right = subRL;
        //检查有没有subRL
        if(subRL!=null) {
            subRL.parent = parent;
        }
        subR.left = parent;
        parent.parent = subR;
        //检查当前是不是根节点
        if(parent==root) {
            root = subR;
            root.parent = null;
        } else {
            if(pParent.left == parent) {
                pParent.left = subR;
            } else {
                pParent.right = subR;
            }
            subR.parent = pParent;
        }
        //更新平衡因子
        subR.bf = parent.bf=0;
    }

    /**
     * 右单旋
     * @param parent
     */
    private void rotateRight(TreeNode parent) {
        TreeNode subL = parent.left;
        TreeNode subLR=subL.right;
        //记录一下parent的父亲节点
        TreeNode pParent = parent.parent;
        parent.left = subLR;
        //检查有没有subLR
        if(subLR!=null) {
            subLR.parent = parent;
        }
        subL.right = parent;
        parent.parent = subL;
        //检查当前是不是根节点
        if(parent == root) {
            root = subL;
            root.parent = null;
        } else {
            //不是根节点，判断这棵子树是左子树还是右子树
            if(pParent.left == parent) {
                pParent.left = subL;
            } else {
                pParent.right = subL;
            }
            subL.parent = pParent;
        }
        //更新平衡因子
        subL.bf = parent.bf = 0;
    }

    /**
     * 验证是否为二叉平衡树
     * @param root
     * @return
     */
    public boolean isBalance(TreeNode root) {
        if(root == null) {
            return true;
        }
        int leftH = height(root.left);
        int rightH = height(root.right);
        if(rightH-leftH!=root.bf) {
            System.out.println("平衡因子异常 "+root.val);
            return false;
        }
        return Math.abs(rightH-leftH)<=1&&isBalance(root.left)&&isBalance(root.right);

    }
    /**
     * 求树的高度
     */
    private int height(TreeNode root) {
        if(root == null) {
            return 0;
        }
        int leftH =height(root.left);
        int rightH = height(root.right);
        return leftH>rightH?leftH+1:rightH+1;
    }


    public static void main(String[] args) {
        AVLTree avlTree1 = new AVLTree();
        AVLTree avlTree2 = new AVLTree();
        int[] arr1 ={16, 3, 7, 11, 9, 26, 18, 14, 15};
        int[] arr2 ={4, 2, 6, 1, 3, 5, 15, 7, 16,14};
        for(int i=0;i<arr1.length;i++) {
            avlTree1.insert(arr1[i]);
        }
        System.out.println(avlTree1.isBalance(avlTree1.root));
        for(int i=0;i<arr2.length;i++) {
            avlTree2.insert(arr2[i]);
        }
        System.out.println(avlTree2.isBalance(avlTree2.root));
    }
}
